討論過這麼多種演算法之後，會發現操作時常常會使用陣列或是某些資料結構。資料結構是指電腦中管理資料的特定方式，有助於資料的運用，選擇適合的結構也可以增進演算法效率。

接下來幾回會討論幾種資料結構以及它們的特性和適合的情境。

陣列與鏈結串列

我們學習程式最早接觸的、每天都會操作的資料結構，可能就是陣列。陣列通常是由相同類型元素組成的資料集合。每當使用陣列，陣列中的元素就會被存在連續的記憶體中，所以我們可以用索引(index)來知道元素的儲存位址。

鏈結串列是一種線性資料結構，其中的元素並不會儲存在連續的記憶體中。鏈結串列的元素被稱作節點(node)，以最簡單的結構來說，每一個節點都會包含儲存的值，以及下一個節點的位址(reference)。這樣一來，節點未必會在相連的位址，所以我們必須依循節點的順序才能存取特定節點。

關於兩種結構儲存方式的差異，Grokking Algorithms這本書裡提供了蠻好懂得比喻。書中提到這就像去電影院看電影，陣列就像是一群朋友堅持座位要連在一起，所以一定要有至少跟人數一樣多的相連位置才有辦法買到票；鏈結串列就像是一群朋友接受分開坐，所以只要電影院內有足夠位子就可以坐進去。

所以當我們在選擇要使用陣列或鏈結串列，可以考慮它們的特性會如何影響特定操作的時間。

新增與刪除

如果建立一個購物清單，可能隨時需要在資料中插入或刪除項目。

使用陣列的話，插入或刪除元素成本會比較高。如果與陣列相鄰的記憶體已有別的資料，在插入新的元素時就必須將整個陣列移到可以容納新陣列的記憶體位址。解決這個問題的一種方式，是先將長度定在資料量可能的上限，但這麼做往往浪費更多記憶體。而刪除雖然沒有記憶體不夠的問題，可是刪除一個元素，代表後面的所有元素都要往前移，所以在陣列中不管是插入或刪除元素，最壞情況的執行時間都是O(n)。

如果換成使用鏈結串列，插入或刪除元素都相對簡單，在已知節點位址的情況下，插入或刪除都只需要O(1)，因為只需要改變節點指向的位址即可。

存取資料

如果一份資料的大小相對固定，但常常要修改資料，我們會需要能夠快速找到特定資料的位址。

這時候陣列的索引就可以實現隨機存取(random access)，讓我們以O(1)存取任意的元素。但鏈結串列就只能夠進行循序存取(sequential access)，也就是只能夠線性地從第一個節點知道第二個節點的位址，再從第二個點知道第三個節點的位址...所以執行時間為O(n)。

綜上所述，陣列的優勢在於：

• 可以隨機存取，資料調用或修改速度較快，因此執行一些需要操作特定元素的演算法會更有效率(例如像二分搜尋要找到陣列的中間元素，或快速排序需要隨機的基準值)。

• 以同樣長度的資料來說，陣列需要的空間更少，因為不需要儲存每個元素的位址。

鏈結串列的優勢則在於：

• 不需要連續的記憶體讓鏈結串列的長度有彈性，所以適合不確定資料大小，或資料大小會頻繁變動的情境，可以在執行時隨著資料增加而逐步增加。

• 也因為上述原因，鏈結串列較易於插入或刪除元素。